#ifndef __MALLOCCOMMON_H__
#define __MALLOCCOMMON_H__

#include <iostream>
#include <algorithm>
#include <assert.h>
#include <thread>
#include <mutex>
#include <cstring>
#include "objectPool.h"
#include "qsingleton.h"
#include "common.h"

#ifdef _WIN32
#include <windows.h>
#else 
#include <sys/mman.h>
#endif


#define  MAX_BYTES 64 * 1024
#define NFREELIST_LEN 184
#define PAGE_SHIFT 12//页单位4kb = 2的23次方
#define  PAGE_NUM 129

static inline void* SystemAlloc(size_t size)
{
#ifdef _WIN32
	void *ptr = VirtualAlloc(0, kpage*(1 << PAGE_SHIFT), MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
  void* ptr = nullptr;
  ptr = mmap(nullptr, size, PROT_READ | PROT_WRITE, MAP_ANONYMOUS | MAP_PRIVATE, -1, 0);
  if(ptr == MAP_FAILED)
  {
    throw std::bad_alloc();
    //return nullptr;
  }
#endif
  if (!ptr)
  {
	  throw std::bad_alloc();
	  //return nullptr;
  }

  return ptr;
}

static inline void SystemFree(void* ptr, size_t size)
{
#ifdef _WIN32
	VirtualFree(ptr, 0, MEM_RELEASE);
#else
  munmap(ptr, size);
#endif
}

//获取链表下一个obj，用内存空间保存
static inline void*& NextObj(void* obj){
	//返回前面指针大小
	//取obj前4/8字节的值，保存的是下一个内存的指针
	return *((void**)obj);
}

class SizeClass
{
	//防止由于对齐数太小导致threadcache哈希桶太大，将哈希桶划分多个区间，每个区间对齐数不同。如下：
	//[1, 128]字节，				对齐数8，	区间个数为[0, 15]		16个
	//[129, 1024]字节，			对齐数16，	区间个数为[16, 71]		56个
	//[1025, 8*1024]字节，		对齐数128，	区间个数为[72, 127]		56个 
	//[8*1024+1, 64*1024]字节，	对齐数1024，	区间个数为[128, 183]		56个
private:
	static size_t index(size_t size, size_t n)
	{
		//（1<<n）为对齐数，size加（对齐数-1），(<<n )除以对齐数得到对应索引
		//减1是因为数组索引从0开始
		//是为了让不是对齐数倍数的会到下一个对齐数倍数，并且正好为对齐数倍数的也不会为下一个倍数。
		// 如果直接除以对齐数，5/8-1为负数，越界了。
		return ((size + ((1 << n) - 1)) >> n) - 1;
	}

	static size_t roundUp(size_t size, size_t n)
	{
		//将size向上取整到对齐数的整数倍
		//size加(对齐数-1)，让不是对齐数倍数的会到下一个对齐数倍数，比如 5不到对齐数8的整数倍
		//&~((1 << n) - 1)， 让后面几位无效，这样就向上取整到对齐数的整数倍了
		//比如：如果8进制~((1 << n) - 1) 二进制为 1111 1111 1111 1111 1111 1111 1111 1000，让后面3位无效，直接向上对齐
		//对齐到16的整数倍，让后4位无效，对齐到128整数倍，让后7位无效。。。。
		return (size + ((1 << n) - 1)) & (~((1 << n) - 1));
	}
public:
	static size_t getIndex(size_t size)
	{
		if (size > MAX_BYTES || size <= 0)
		{
			return -1;
		}

		//哈希桶区间个数
		size_t range_num[] = { 16, 56, 56, 56 };

		//计算出每个区间距离区间起始位置的距离，加上之前的区间个数，就是当前位置
		//size为什么要减去前面区间size大小？
		//因为前面区间对齐数不一样，
		//index函数是求出了这个区间从0开始的索引，所以需要加三个前面区间个数
		if (size <= 128)
		{
			return index(size - 0, 3);
		}
		else if (size <= 1024)
		{
			return index(size - 128, 4) + range_num[0];
		}
		else if (size <= 8192)
		{
			return index(size - 1024, 7) + range_num[1] + range_num[0];
		}
		else if (size <= 65536)
		{
			return index(size - 8192, 10) + range_num[2] + range_num[1] + range_num[0];
		}
    return 0;
	}

	//获得size对应区间向上取整的对齐数整数倍
	static size_t getRoundUp(size_t size)
	{
		if (size <= 128)
		{
			return roundUp(size, 3);
		}
		else if (size <= 1024)
		{
			return roundUp(size, 4);
		}
		else if (size <= 8192)
		{
			return roundUp(size, 7);
		}
		else if (size <= 65536)
		{
			return roundUp(size, 10);
		}
    else 
    {
      return roundUp(size, PAGE_SHIFT);
    }
    return 0;
	}

	//size对应申请内存块的个数
	static size_t SizeMoveNum(size_t size)
	{
		//size越大，num越少，size越小，num越大
		size_t num = MAX_BYTES / size;
		if (size <= 0)
			return 2;

		if (num >= 512)
			return 512;
		
		return num;
	}

	//size获取到页数
	static size_t SizeMovePage(size_t size)
	{
		//threadCache需要内存块个数
		size_t num = SizeMoveNum(size);
		//总共需要的大小
		size_t totalnum = num * size;

		//需要的页数
		size_t pagenum = totalnum >> PAGE_SHIFT;
		if (pagenum <= 0)
			pagenum = 1;//最少一页

		return pagenum;
	}
};


class FreeList
{
public:
	FreeList()
		: head_(nullptr)
		, num_(0)
		, max_num_(1)
	{}

	//~FreeList()
	//{
	//	head_ = nullptr;
	//	num_ = 0;
	//	max_num_ = 0;
	//}

	size_t getNum()
	{
		return num_;
	}

	size_t getMaxNum()
	{
		return max_num_;
	}

	void setMaxNum(size_t num)
	{
		max_num_ = num;
	}

	bool empty()
	{
		return head_ == nullptr;
	}

	void* pop()
	{
		void* obj = head_;
		head_ = NextObj(obj);
    if(num_ >= 0)
		  num_--;
    //std::cout << "threadCache num: " << num_ << std::endl;
		return obj;
	}

	size_t popRange(void*& start, void*& end, size_t num)
	{
    if(num == 0)
    {
      return 0;
    }

		if (num > num_)
			num = num_;

		size_t actualnum = 0;
		start = head_;
		for (size_t i = 0; head_ && i< num; ++i)
		{
			end = head_;
			head_ = NextObj(head_);
			actualnum++;
		}

		//while (num > 0 && num-- && head_)
		//{
		//	end = head_;
		//	head_ = NextObj(head_);
		//	actualnum++;
		//}

    NextObj(end) = nullptr;
    for(size_t i = 0; num_ && i < actualnum; ++i)
    {
      num_--;
    }
    //std::cout << "threadCache num: " << num_ << std::endl;
		return actualnum;
	}

	void push(void* ptr)
	{
		//头插
		NextObj(ptr) = head_;
		head_ = ptr;
		num_++;
    //std::cout << "threadCache num: " << num_ << std::endl;
	}

	void pushRange(void* start, void* end, size_t n)
	{
		NextObj(end) = head_;
		head_ = start;
		num_ += n;
    //std::cout << "threadCache num: " << num_ << std::endl;
	}

private:
	void* head_;//哈希表链表头节点
	size_t num_;
	size_t max_num_;//为了控制从centralCache中申请个数
};

typedef size_t Pageid;
struct Span
{
	Span()
	{
		next_ = nullptr;
		prev_ = nullptr;
		size_ = 0;
		usenum_ = 0;
		pageid_ = 0;
		n_ = 0;
		list_ = nullptr;
	}
	//~Span()
	//{
	//	next_ = nullptr;
	//	prev_ = nullptr;
	//	usenum_ = 0;
	//	pageid_ = 0;
	//	list_ = nullptr;
	//}

	Pageid pageid_;//页编号
	size_t n_;//有多少页
	size_t size_;//切割后的内存块大小

	Span* next_;
	Span* prev_;

	void* list_;//大内存块
	size_t usenum_;//使用了多少内存块
};


#ifdef _SPANPOOL
  typedef OBJECT::objectPool<Span, OBJECT::heapAllocator<Span> > OBJECTPOOLHEAPT;
  typedef OBJECT::objectPool<Span, OBJECT::vectorAllocator<Span> > OBJECTPOOLVECTORT;
  extern OBJECTPOOLVECTORT span_object_pool_;
#endif


  class SpanList
  {
  public:
	  SpanList()
	  {
#ifdef _SPANPOOL
		  head_ = span_object_pool_.allocate(sizeof(Span));
#else
		  head_ = (Span*)SystemAlloc(sizeof(Span));
		  new (head_)Span();
#endif 
		  head_->next_ = head_;
		  head_->prev_ = head_;
	  }
	  //~SpanList()
	  //{
	  //	//Span* obj = head_;
	  //	//while (obj->next_ != head_)
	  //	//{
	  //	//	Span* tmp = obj->next_;
	  //	//	delete obj;
	  //	//	obj = tmp;
	  //	//}
	  //   head_->~Span();
	  //   SystemFree(head_, sizeof(Span));
	  //	//delete head_;
	  //}

	  bool empty()
	  {
		  return head_->next_ == head_;
	  }

	  void pushFront(Span* sp)
	  {
		  assert(sp->pageid_ && sp->n_);
		  Span* next = head_->next_;
		  head_->next_ = sp;
		  sp->prev_ = head_;
		  sp->next_ = next;

		  next->prev_ = sp;
	  }

	  Span* popFront()
	  {

		  Span* sp = head_->next_;
		  Span* next = sp->next_;

		  head_->next_ = next;
		  next->prev_ = head_;
		  assert(sp->pageid_ && sp->n_);
		  return sp;

		  //Span* next = head_->next_;
		  //head_->next_ = next->next_;
		  //next->next_->prev_ = head_;

		  //return next;
	  }

	  void erase(Span* sp)
	  {
		  assert(sp != head_);
		  Span* prev = sp->prev_;
		  Span* next = sp->next_;
      if(!prev || !next)
        return;
		  prev->next_ = next;
		  next->prev_ = prev;
	  }

	  //遍历
	  Span* begin()
	  {
		  return head_->next_;
	  }
	  Span* end()
	  {
		  return head_;
	  }

	  //qMutex& getMutex()
	  //{
	  //return mt_;
	  //}

	  //std::mutex mt_;
	  //每一个桶一个锁
	  qMutex mt_;
  private:
	  //带头双向链表
	  Span* head_;

  };

  //在当前的__x86_64__处理器中，只用了地址的低48bits用于虚拟和物理地址的转换，高16bits是不用的
  //一页2^12 = 4kb，总共有2^36页(2^(48－12))
  static const size_t BITS = 64  - 12; //36
  //3层基数树
  //高11位做第一层，中间12位做第二层，低12位做第三层 
  class PageMap3
  {
  private:
	  static const size_t leafbit_ = (BITS + 2) / 3;//第一层位数12
	  static const size_t leaflength_ = 1 << leafbit_;//第一层长度
	  
	  static const size_t midbit_ = (BITS + 2) / 3;//第二层位数12
	  static const size_t midlength_ = 1 << midbit_;//第二层长度

	  static const size_t rootbit_ = BITS - leafbit_ - midbit_;//第三层位数11
	  static const size_t rootlength_ = 1 << rootbit_;//第三层长度 默认加1了(数组大小) 例如：rootbit为1位 1<<1=2

	  struct Leaf
	  {
		  Leaf()
		  :spans_{}
		  {}
		  //第三层
		  Span* spans_[leaflength_];
	  };

	  struct Node
	  {
		  Node()
		  :leafs_{}
		  {}
		  //第二层
		  Leaf* leafs_[midlength_];
	  };
	  //第一层
	  Node* root_[rootlength_];

  public:
	  PageMap3()
		  :root_{}
	  {
		  //实现在需要时才开空间，在pageCache getSpan时开空间，开最大的
		 /* for (size_t i = 0; i < rootlength_; ++i)
		  {
			  root_[i] = (Node*)SystemAlloc(sizeof(Node));
			  for (size_t j = 0; j < midlength_; ++j)
			  {
				  root_[i]->leafs_[j] = (Leaf*)SystemAlloc(sizeof(Leaf));
				  new (root_[i]->leafs_[j]) Leaf();
			  }
		  }*/
	  }
	  
	  //start_attr起始地址，n地址个数
	  bool ensure(size_t start_pagid, size_t n)
	  {
		  for (size_t k = start_pagid; k <= start_pagid + n - 1;)
		  {
			  size_t i1 = k >> (leafbit_ + midbit_);
			  if (i1 >= rootlength_)
				  return false;

			  if (root_[i1] == nullptr)
			  {
				  Node* node = reinterpret_cast<Node*>(SystemAlloc(sizeof(Node)));
				  if (node == nullptr)
					  return false;

				  memset(node, 0, sizeof(Node));
				  root_[i1] = node;
			  }

			  size_t i2 = (k >> leafbit_) & (midlength_ - 1);
			  if (i2 >= midlength_)
				  return false;

			  if (root_[i1]->leafs_[i2] == nullptr)
			  {
				  Leaf* leaf = reinterpret_cast<Leaf*>(SystemAlloc(sizeof(Leaf)));
				  if (leaf == nullptr)
					  return false;

				  memset(leaf, 0, sizeof(Leaf));
				  root_[i1]->leafs_[i2] = leaf;
			  }

			  //前进一个第三层的一个节点
			  //因为这个节点已经创建
			  k = ((k >> leafbit_) + 1) << leafbit_;
		  }
      return true;
	  }

	  Span* getSpan(size_t pageid)
	  {
		  const size_t i1 = pageid >> (leafbit_ + midbit_);//得到高位索引
		  const size_t i2 = (pageid >> leafbit_) & (midlength_ - 1);//取中间层索引，按位与&相当于取余操作，midlength_ - 1避免超过数组上限
		  const size_t i3 = pageid & (leaflength_ - 1);//同理，取第三层索引位置

		  assert(pageid >> BITS <= 0 && root_[i1] && root_[i1]->leafs_[i2]);
		  //if (pageid >> BITS > 0 || root_[i1] == nullptr ||
			 // root_[i1]->leafs_[i2] == nullptr)
			 // return nullptr;
      //if(root_[i1]->leafs_[i2]->spans_[i3])
        //printf("getSpan: %p : %lu, %lu, %lu\n", root_[i1]->leafs_[i2]->spans_[i3], pageid, root_[i1]->leafs_[i2]->spans_[i3]->size_, pthread_self());
      //else 
        //std::cout << "getSpan: nullptr " << i1 << ":" << i2 << ":" << i3 << std::endl;

		  return root_[i1]->leafs_[i2]->spans_[i3];
	  }

	  //删除也用这个sp传nullptr
	  void setSpan(size_t pageid, Span* sp)
	  {
		  assert(pageid >> BITS <= 0);

		  const size_t i1 = pageid >> (leafbit_ + midbit_);//得到高位索引
		  const size_t i2 = (pageid >> leafbit_) & (midlength_ - 1);//取中间层索引，按位与&相当于取余操作，midlength_ - 1避免超过数组上限
		  const size_t i3 = pageid & (leaflength_ - 1);//同理，取第三层索引位置
		  root_[i1]->leafs_[i2]->spans_[i3] = sp;
      //std::cout << "setSpan: " << sp << ":" << pageid << ":" << sp->n_ << ":" << sp->size_ << std::endl;
	  }

	  //Span*& operator[](size_t pageid)
	  //{
		 // assert(pageid >> BITS <= 0);

		 // const size_t i1 = pageid >> (leafbit_ + midbit_);//得到高位索引
		 // const size_t i2 = (pageid >> leafbit_) & (midlength_ - 1);//取中间层索引，按位与&相当于取余操作，midlength_ - 1避免超过数组上限
		 // const size_t i3 = pageid & (leaflength_ - 1);//同理，取第三层索引位置

		 // return root_[i1]->leafs_[i2]->spans_[i3];
	  //}

	  void erase(size_t pageid)
	  {
		  assert(pageid >> BITS <= 0);

		  const size_t i1 = pageid >> (leafbit_ + midbit_);//得到高位索引
		  const size_t i2 = (pageid >> leafbit_) & (midlength_ - 1);//取中间层索引，按位与&相当于取余操作，midlength_ - 1避免超过数组上限
		  const size_t i3 = pageid & (leaflength_ - 1);//同理，取第三层索引位置

      //if(root_[i1]->leafs_[i2]->spans_[i3])
      //  std::cout << "getSpan: " << root_[i1]->leafs_[i2]->spans_[i3] << ":" << pageid << ":" << root_[i1]->leafs_[i2]->spans_[i3]->size_ << std::endl;
      //else 
      //  std::cout << "getSpan: nullptr " << i1 << ":" << i2 << ":" << i3 << std::endl;

		  root_[i1]->leafs_[i2]->spans_[i3] = nullptr;
	  }


  };



#endif
